package com.songyang.yougnsql.core.version;

import com.songyang.yougnsql.common.ErrorMsg;
import com.songyang.yougnsql.common.YoungSQLException;

import java.util.*;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

/**
 * @ClassName LockTable 锁图
 * @Description 维护了一个依赖等待图，以进行死锁检测
 * @date 2022/12/16 10:41
 * @Author yanceysong
 * @Version 1.0
 */
public class LockMap {
    /**
     * 某个XID已经获得的资源的UID列表
     */
    private final Map<Long, List<Long>> xidAcquireUid;
    /**
     * UID被某个XID持有
     */
    private final Map<Long, Long> uidBelongXid;
    /**
     * 正在等待UID的XID列表
     */
    private final Map<Long, List<Long>> uidWaitList;
    /**
     * 正在等待资源的XID的锁
     */
    private final Map<Long, Lock> waitLock;
    /**
     * XID正在等待的UID
     */
    private final Map<Long, Long> xidWaitUid;
    private final Map<Long, Integer> xidStamp;
    private int stamp;
    private final ReentrantLock lock;

    public LockMap() {
        xidAcquireUid = new HashMap<>();
        uidBelongXid = new HashMap<>();
        waitLock = new HashMap<>();
        uidWaitList = new HashMap<>();
        xidWaitUid = new HashMap<>();
        xidStamp = new HashMap<>();
        lock = new ReentrantLock();
    }

    /**
     * 当一个事务commit或者abort时候，释放所有他持有的锁，并将自身从等待图中删除
     *
     * @param xid 事务的id
     */
    public void remove(long xid) {
        lock.lock();
        try {
            //移除这个xid获取
            LinkedList<Long> uidList = (LinkedList<Long>) xidAcquireUid.get(xid);
            while (uidList != null && uidList.size() > 0) {
                //释放xid获取的uid
                Long uid = uidList.removeLast();
                //被释放的uid选择一个xid是争抢它
                selectNewXidToAcquire(uid);
            }
            xidWaitUid.remove(xid);
            xidAcquireUid.remove(xid);
            waitLock.remove(xid);
        } finally {
            lock.unlock();
        }
    }

    /**
     * 1、判断当前事务T获取的资源是不是已经在之前被本身事务T获取，如果是返回null(可重入)
     * 2、如果当前资源在之前没有被当前事务获取过，那么判断当前资源是否被其它事务占有，
     * 如果没有被其它事务占用，那么当前事务占有该数据,并且放入u2x与x2u
     * 如果不满足上面两个条件
     * 1、把当前事务放入waitLock与xidWaitUid中
     * 2、然后进行死锁检测，如果添加过后存在死锁那么需要移除刚添加的并抛出异常
     *
     * @param xid 事务的id
     * @param uid 数据的id
     * @return 不需要等待则返回null，否则返回锁对象
     * @throws Exception 会造成死锁则抛出异常
     */
    public Lock add(long xid, long uid) throws Exception {
        lock.lock();
        try {
            //如果这个资源已经被该事务争取过了
            if (isInAcquireList(xidAcquireUid, xid, uid)) {
                return null;
            }
            //如果该资源没有被任何事物争取过
            if (!uidBelongXid.containsKey(uid)) {
                uidBelongXid.put(uid, xid);
                putIntoXidAcquireUid(xidAcquireUid, xid, uid);
                return null;
            }
            //从现在开始，xid正确uid失败
            //放入xid正在等待的uid列表
            xidWaitUid.put(xid, uid);
            //放入uid被等待的xid列表
            putIntoUidWaitList(uidWaitList, uid, xid);
            //接下来看是判断死锁
            if (hasDeathLock()) {
                xidWaitUid.remove(xid);
                removeOutUidWaitList(uidWaitList, uid, xid);
                throw new YoungSQLException(ErrorMsg.DEAD_LOCK_EXCEPTION);
            }
            ReentrantLock newLock = new ReentrantLock();
            newLock.lock();
            waitLock.put(xid, newLock);
            return newLock;
        } finally {
            lock.unlock();
        }
    }

    /**
     * 当一个xid已经commit以后，该xid下的所有uid的等待者可以释放。
     * 在选择的时候，按照先进先出队列的策略进行唤醒
     *
     * @param uid 资源的id
     */
    private void selectNewXidToAcquire(long uid) {
        //删除，代表这个uid不再被这个xid锁占有
        uidBelongXid.remove(uid);
        //获取等待这个uid的xid列表
        LinkedList<Long> xidList = (LinkedList<Long>) uidWaitList.get(uid);
        if (xidList == null || xidList.size() <= 0) {
            return;
        }
        while (xidList.size() > 0) {
            //队列的方式去找一个xid去占有自己
            Long xid = xidList.remove();
            if (waitLock.containsKey(xid)) {
                uidBelongXid.put(uid, xid);
                Lock xidLock = waitLock.remove(xid);
                //找到xid获取的锁去唤醒
                xidLock.unlock();
                break;
            }
        }
        if (xidList.size() == 0) {
            uidWaitList.remove(uid);
        }
    }

    /**
     * 当发生了死锁，将资源等待的列表移除这个xid
     *
     * @param uidWaitList uid等待xid的列表
     * @param uid         资源的id
     * @param xid         事务的id
     */
    private void removeOutUidWaitList(Map<Long, List<Long>> uidWaitList, long uid, long xid) {
        Optional.ofNullable(uidWaitList.get(uid)).ifPresent(xidList -> {
            xidList.remove(xid);
            if (xidList.size() == 0) {
                uidWaitList.remove(uid);
            }
        });
    }

    /**
     * 判断是否已经发生了死锁
     * <p>
     * 图不一定是连通图。思路就是为每个节点设置一个访问戳
     * 都初始化为 null，随后遍历所有节点，以每个非 null 的节点作为根进行深搜，
     * 并将深搜该连通图中遇到的所有节点都设置为同一个数字，不同的连通图数字不同。
     * 这样，如果在遍历某个图时，遇到了之前遍历过的节点，说明出现了环。
     *
     * @return 结果
     */
    private boolean hasDeathLock() {
        /*
         * 产生死锁举例：
         *  如果a获取资源x1然后获取x2即:a => x1 => x2
         *  如果b获取资源x2然后获取x1即:b => x2 => x1
         *  那么在a获取好了x1，b获取好了x2之后就会产生死锁。
         *  这个时候的图如下：("---"代表想要争取的关系，"|"代表已经获取的关系)
         *  x1 ---- b
         *  |       |
         *  a ---- x2
         *  即，a要争取x2的锁，x2又被b获取，b要争取x1的锁，而x1又被a获取，图产生了换，则判定为产生了死锁
         */

        //初始的戳
        stamp = 1;
        //遍历所有的xid，其实判断xidWaitUid速度可能更快一点，后面测试一下
        //todo 测试xidWaitUid
        for (long xid : xidAcquireUid.keySet()) {
            Integer xidNowStamp = xidStamp.get(xid);
            //如果这个xid已经被验证过了，就不再验证
            if (xidNowStamp != null && xidNowStamp > 0) {
                continue;
            }
            //更新一下新的时间戳
            stamp++;
            //判断是否产生了环
            if (dfs(xid)) {
                return true;
            }
        }
        return false;
    }

    /**
     * dfs深度搜索，判断图中是否产生了环来验证是否产生了死锁
     *
     * @param xid 事务的id
     * @return 搜索结果
     */
    private boolean dfs(long xid) {
        Integer xidNowStamp = xidStamp.get(xid);
        //如果这个图被访问过了，则出现了环，产生了死锁
        if (xidNowStamp != null && xidNowStamp == stamp) return true;
        //因为stamp一直在正序自加，如果发现这个戳比现在的小，说明一件被检查过了，这个xid没有产生死锁
        if (xidNowStamp != null && xidNowStamp < stamp) return false;
        xidStamp.put(xid, stamp);
        //获取这个xid正在等待的uid
        Long waitUid = xidWaitUid.get(xid);
        //查看这个uid已经被那个xid正在获取
        Long uid2xid = uidBelongXid.get(waitUid);
        //查看uid属于的xid是否与刚才的xid产生了环。
        return dfs(uid2xid);
    }

    /**
     * 如果xid成功获取某个资源，则将这对信息记录下来
     *
     * @param xidAcquireUid 记录的列表map
     * @param xid           事务的id
     * @param uid           资源的id
     */
    private void putIntoXidAcquireUid(Map<Long, List<Long>> xidAcquireUid, long xid, long uid) {
        if (!xidAcquireUid.containsKey(xid)) {
            xidAcquireUid.put(xid, new LinkedList<>());
        }
        xidAcquireUid.get(xid).add(uid);
    }

    /**
     * 当事务获取某个资源失败，则将该信息记录下来
     *
     * @param uidWaitList 正在等待uid的xid列表
     * @param xid         事务的id
     * @param uid         资源的id
     */
    private void putIntoUidWaitList(Map<Long, List<Long>> uidWaitList, long uid, long xid) {
        if (!uidWaitList.containsKey(uid)) {
            uidWaitList.put(uid, new LinkedList<>());
        }
        uidWaitList.get(uid).add(xid);
    }

    /**
     * 判断某个uid是否已经被xid获取过
     *
     * @param xidAcquireUid 获取的列表
     * @param xid           事务的id
     * @param uid           数据的id
     * @return 结果
     */
    private boolean isInAcquireList(Map<Long, List<Long>> xidAcquireUid, long xid, long uid) {
        List<Long> acquiredUid = xidAcquireUid.get(xid);
        return acquiredUid != null && acquiredUid.contains(uid);
    }
}
